<!DOCTYPE html>
<html lang="en">
<head>
  <title>玩转链表</title>
  <meta charset="UTF-8">
  <meta name="description" content="ltoddy's blog">
  <meta name="author" content="liutao">
  <meta name="author" content="ltoddy">
  <meta name="author" content="just for fun">

  <link rel="stylesheet" href="../../static/css/bootstrap.css">
  <link rel="stylesheet" href="../../static/css/bootstrap-theme.css">
  <link rel="icon" href="../../static/me.jpg">

  <script src="../../static/js/jquery-3.2.1.min.js"></script>
  <script src="../../static/js/bootstrap.js"></script>
</head>
<body>
<a href="https://github.com/ltoddy/ltoddy.github.io" target="_blank"><img
    style="position: absolute; top: 0; right: 0; border: 0;"
    src="https://camo.githubusercontent.com/38ef81f8aca64bb9a64448d0d70f1308ef5341ab/68747470733a2f2f73332e616d617a6f6e6177732e636f6d2f6769746875622f726962626f6e732f666f726b6d655f72696768745f6461726b626c75655f3132313632312e706e67"
    alt="Fork me on GitHub"
    data-canonical-src="https://s3.amazonaws.com/github/ribbons/forkme_right_darkblue_121621.png">
</a>
<div class="container">
  <div class="page-header">
    <h3>玩转链表</h3>
  </div>
  <p> 在scheme中有这么一个基本过程:cons,以及car和cdr<br></p>
  <p>
    <small>e.g.</small>
  </p>
  <pre><code>#lang scheme
(define lst (cons 1 2))
(car lst)    ; 输出1
(cdr lst)    ; 输出2</code></pre>
  <p> cons用来构造一个序偶,也就是C++里面中的pair,car是获取cons中第一个元素(相当于pair中的first),cdr是获取cons中第二个元素(相当于pair中的second).</p>
  <p> 名字cons表示"构造"(construct)。名字car和cdr则来自Lisp最初在IBM
    704机器上实现。在这种机器有一种取址模式,使人可以访问一个存储地址中"地址"(address)部分和"减量"(decrement)部分.</p>
  <ul>
    <li>car表示"Contents of Address part of Register"(寄存器的地址部分的内容)</li>
    <li>cdr(读作 "could-er")表示"Contents of Decrement part of Register"(寄存器的减量部分的内容)</li>
  </ul>
  <p> 也就是说一个序列可以通过嵌套的cons操作构造出来</p>
  <p>
    <small>e.g.</small>
  </p>
  <pre><code>
#lang scheme
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 null)))))
</code></pre>

  <p>
    <small>输出&gt;</small>
    <code>(1 2 3 4 5)</code></p>
  <p>通过嵌套的cons形成的这样一个序列也就是所谓的链表.</p>

  <h4>Python实现:</h4>
  <pre><code>
#!/usr/bin/python3
def cons(car, cdr):
    return lambda x: car if x else cdr


def printer(l):
    if l is None:
        print("nil")
    else:
        while l:
            car = l(True)
            print(car, end=' ')
            l = l(False)
        else:
            print()


printer(cons(1, None))
printer(cons(1, cons(2, None)))
printer(cons(1, cons(2, cons(3, None))))
</code></pre>
  <p>
    <small>输出</small>
  </p>
  <pre><code>
1
1 2
1 2 3
</code></pre>
</div>
</body>
</html>